package algorithm_demo.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序
 * <p>
 * 不基于比较的排序，都是根据数据状况的排序
 * <p>
 * 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键在于这个映射函数的确定。为了使桶排序更加高效。我们需要做到这两点：
 * 1. 在额外空间充足的情况下，尽量增大桶的数量；
 * 2. 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中
 * <p>
 * 桶排序的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行）。
 * <p>
 * 算法步骤：
 * 1. 设置一个BucketSize，作为每个桶所能放置多少个不同数值；
 * 2. 遍历输入数据，并且把数据依次映射到对应的桶里去；
 * 3. 对每个非空的桶进行排序，可以使用其他排序方法，也可以递归使用桶排序；
 * 4. 从非空桶里把排好序的数据拼接起来。
 * <p>
 * 算法分析
 * 稳定性 ：稳定
 * 时间复杂度 ：最佳：O(n+k) 最差：O(n²) 平均：O(n+k)
 * 空间复杂度 ：O(k)
 *
 * @author Api
 * @date 2022/11/19 23:12
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr= {72,6,57,88,60,42,83,73,48,105,85,200};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bucketSort(int[] arr){

        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int k : arr) {
            max = Math.max(max, k);
            min = Math.min(min, k);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        List<List<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<>());
        }

        // 将每个元素放入桶
        for (int j : arr) {
            int num = (j - min) / (arr.length);
            bucketArr.get(num).add(j);
        }

        // 对每个桶进行排序
        for (List<Integer> integerArrayList : bucketArr) {
            Collections.sort(integerArrayList);
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for (List<Integer> integers : bucketArr) {
            for (Integer integer : integers) {
                arr[index++] = integer;
            }
        }
    }
}
